
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include "heap.h"
#include "error.h"

struct sheap {
	tcpalpha* arr;
	int size;
	int maxsize;
};

int lSon (int q) {
	assert (q>=0);
	return (2*q+1);
}

int rSon (int q) {
	assert (q>=0);
	return (2*(q+1));
}

int dad (int q) {
	assert (q>0);
	if(q%2==0)
		return ((q/2)-1);
	else
		return (q/2);
}

Bool
hasSon (heap h, int q)
{
	if (2*q+1 > h->size)
		return FALSE;
	else
		return TRUE;
}

int
ySon (heap h, int q)
{
	assert(hasSon(h,q));
	if ( (rSon(q) <= h->size) && (prior_ord(alpha_prior(h->arr[rSon(q)]),alpha_prior(h->arr[lSon(q)]))) )
		return (rSon(q));
	else
		return (lSon(q));
}

Bool
mustRise (heap h, int q)
{
	if (q==0)
		return FALSE;
	else if (prior_ord(alpha_prior(h->arr[q]),alpha_prior(h->arr[dad(q)])))
		return TRUE;
	else
		return FALSE;
}

void
rise (heap h, int q)
{
	tcpalpha aux=NULL;
	assert ((0 < q) && (q <= h->size));
	aux = h->arr[dad(q)];
	h->arr[dad(q)] = h->arr[q];
	h->arr[q] = aux;
}

void
levitate (heap h, int q)
{
	int p;	/* esto es para no tocar los parametros */
	p = q;
	while (mustRise(h,p))
	{
		rise(h,p);
		p = dad(p);
	}
}

void
sink (heap h, int q)
{
	int p;
	p = q;
	while (hasSon(h,p) && mustRise(h,ySon(h,p)))
	{
		p = ySon(h,p);
		rise(h,p);
	}
}

heap
hempty (const int N)
{
	heap h=NULL;

	h = (heap) calloc (1,sizeof(struct sheap));

	if (h==NULL)
		err(EXIT_FAILURE,ERRFMT,"hempty: lack of free memory",__LINE__);

	h->arr = (tcpalpha*) calloc (N+1,sizeof(tcpalpha));

	if (h->arr==NULL)
		err(EXIT_FAILURE,ERRFMT,"hempty: lack of free memory",__LINE__);

	h->size = 0;
	h->maxsize = N;

	return h;
}

heap
hadd (heap h, const tcpalpha a)
{
	tcpalpha aux=NULL;

	if (h==NULL || a==NULL)
		errx(EXIT_FAILURE,ERRFMT,"hadd: heap or element NULL",__LINE__);

	if (!hIsFull(h))
	{
		aux = alpha_clone(a);
		h->arr[h->size] = aux;
		levitate(h,h->size);
		h->size++;
	}
	else
		warnx(ERRFMT,"hadd: heap full",__LINE__);

	return h;
}

Bool
hIsFull (heap h) {
	if (h==NULL)
		err(EXIT_FAILURE,ERRFMT,"hIsFull: nil heap",__LINE__);
	return (h->size == h->maxsize);
}

Bool
hIsEmpty (heap h) {
	if (h==NULL)
		err(EXIT_FAILURE,ERRFMT,"hIsEmpty: nil heap",__LINE__);
	return (h->size == 0);
}

tcpalpha
hroot (const heap h)
{
	tcpalpha a=NULL;	/* hIsEmpty verifica que h!=NULL */
	assert (!hIsEmpty(h));
	a = alpha_clone(h->arr[0]);
	return a;
}

heap
hdel (heap h, int p)
{
	int q=p;
	tcpalpha aux=NULL;
	assert (0<=q && q<h->size);

	if (h->size > 1)
	{
		aux = alpha_clone(h->arr[q]);
		h->arr[q] = alpha_destroy(h->arr[q]);
		h->size = h->size - 1;
		h->arr[q] = alpha_clone(h->arr[h->size]);

		if (prior_ord(alpha_prior(aux),alpha_prior(h->arr[q])))
			sink(h,q);
		else
			levitate(h,q);

		h->arr[h->size] = alpha_destroy(h->arr[h->size]);
		aux = alpha_destroy(aux);
	}
	else
	{
		h->arr[0] = alpha_destroy(h->arr[0]);
		h->size--;
	}

	return h;
}

tcpalpha
htake (heap h)
{
	tcpalpha a=NULL;
	assert(!hIsEmpty(h));
	a = alpha_clone(h->arr[h->size-1]);
	(h->arr[h->size-1]) = alpha_destroy(h->arr[h->size-1]);
	h->size = h->size - 1;
	return a;
}

heap
hdestroy (heap h)
{
	int i=0;
	if (h==NULL)
		return h;
	else
	{
		for (;i < h->maxsize ; i++)
			h->arr[i] = alpha_destroy(h->arr[i]);
		free(h->arr);
		h->arr = NULL;
		free(h);
		h = NULL;
		return h;
	}
}


/*	TEST	
int main (void)
{
	heap h=NULL;
	tcpalpha a=NULL,b=NULL,c=NULL,d=NULL;
	Bool b1=FALSE,b2=TRUE,b3=TRUE,b4=FALSE;
	int i=0;

	h = hempty(3);
	a = alpha_create(1,2,50);
	b = alpha_clone(a);
	c = alpha_create(4,5,100);

	b1 = hIsEmpty(h);
	b2 = hIsFull(h);
	h = hadd(h,a);
	h = hadd(h,b);
	h = hadd(h,c);
	b3 = hIsEmpty(h);
	b4 = hIsFull(h);
	if (b1 && !b2 && !b3 && b4)
		printf("Test agregar/vacio/lleno Superado\n");
	else
		printf("Test agregar/vacio/lleno Fallido\n");

	d = hroot(h);
	i = alpha_prior(d);
	if (i==50)
		printf("Test raiz Superado\n");
	else
		printf("Test raiz Fallido\n");
	d = alpha_destroy(d);

	i = 0;
	h = hdel(h,0);
	d = hroot(h);
	i = alpha_prior(d);
	if (i==50)
		printf("Test delete Superado\n");
	else
		printf("Test delete Fallido\n");
	d = alpha_destroy(d);

	i = 0;
	b1 = TRUE;
	a = alpha_destroy(a);
	b = alpha_destroy(b);
	a = alpha_create(1,10,1000);
	h = hadd(h,a);
	b = htake(h);
	i = alpha_prior(b);
	b1 = hIsFull(h);
	if (i==1000 && !b1)
		printf("Test take Superado\n");
	else
		printf("Test take Fallido\n");

	a = alpha_destroy(a);
	b = alpha_destroy(b);
	c = alpha_destroy(c);
	d = alpha_destroy(d);
	h = hdestroy(h);
	if (h==NULL)
		printf("Test destroy Superado\n");
	else
		printf("Test destroy Fallido\n");

	return 0;
}*/
